Soon after the introduction of its basic concept, network coding was accepted as a promising technique for multicast and attracted a lot of attention in the research community. As opposed to conventional packet networks where intermediate nodes can only store and forward the incoming packets, in network coding the intermediate nodes can also combine the incoming packets to form (encode) an outgoing packet. Later, the idea of linearly combining the incoming packets was introduced and extended by using an algebraic approach. Also, by proposing random linear network coding (RLNC), network coding was later shown to be an attractive technique for multicast over networks with random topology.
In RLNC, the source node and all the other intermediate nodes of the network encode the data packets by forming random linear combinations of them. The receivers then wait to receive enough encoded packets, in other words enough linear combinations of the information packets, such that they can form a full rank system of linear equations. Each receiver can now decode the information packets by solving its received system of linear equations. It has been shown that by using RLNC with sufficiently large code alphabet q, it is possible to achieve zero reception overhead with failure probability arbitrary close to zero. The encoding complexity of RLNC for a block of K information packets each with s symbols is O(Ks) operations per coded packet where the operations are done in GF(q). The complexity of decoding then scales as O(K2+Ks) per information packet which becomes impractical when the block size K is moderate to large.
To reduce the decoding complexity of network coding, the idea of fragmenting the information packet blocks into distinct generations was proposed. This way, random linear combinations are formed only within each generation. This makes the final linear equation system solvable locally within each generation and thus sparse. This technique, however, requires a large number of control messages to be exchanged between the nodes to combat the problem of rare blocks and block reconciliation. To avoid this, a method called sparse RLNC (SRLNC) was proposed. This method uses a simple random schedule for selecting which generation to transmit at any time. This method reduces the encoding complexity to O(gs) per coded packet and the decoding complexity to O(g2+gs) per information packet, where g denotes the number of information packets in each generation This complexity is practically feasible if s is not very large, making SRLNC an attractive solution for multicast. Unfortunately, the reception overhead under this scheme is affected by the curse of coupon collector phenomenon and thus even for very large alphabet size or number of information packets, the reception overhead does not vanish. In fact, the reception overhead grows with K as O(logK) for sufficiently large number of generations. Consequently, a trade-off is raised between reception overhead and complexity in SRLNC.
It should be noted that, for this document, the reception overhead is defined as the difference between the number of received packets required for successful decoding and the number of information packets divided by the number of information packets. As well, it should be noted that throughout this document, the discussion is limited to the case where all generations are of the same size.
In general, the large reception overhead in SRLNC comes from two sources. The first and major source comes from random scheduling, the fact that the receiver needs to keep listening to the network until it receives enough packets in each generation to be able to decode them. As a result, the number of received packets varies across different generations and to ensure that all generations have enough packets may require a large number of total received packets. In other words, assuming that generations are of size g, for all generations to become full rank, some generations will receive significantly more than g packets resulting in a large reception overhead. The second source of reception overhead is due to the possibility of receiving linearly dependent combinations of the packets which do not bring new information for the decoder. The probability of receiving these linearly dependant equations can be arbitrarily reduced by increasing the field size q of the code alphabet. Another solution proposed is to perform pre-coding using maximum rank distance codes which is quite effective even for very small field sizes.
Knowing that SRLNC is complexity-efficient, there have been several attempts to decrease their reception overhead. For this purpose, the idea of using an outer code is introduced. In this method, an outer code which is considered as a separate block is applied to SRLNC. At the receiver, the outer decoder waits for the recovery of 1−δ fraction of the generations for some small predefined δ and then participates in the decoding to recover the remaining δ fraction of the generations. This method is capable of reducing the reception overhead to a constant, independent of K. However, this scheme is still wasteful in terms of the reception overhead since it ignores the received packets pertaining to the δ fraction of the generations. Furthermore, waiting to receive enough packets to recover 1−δ fraction of the generations when δ is small leads to a high probability of receiving more than g packets in some generations. As a result, the reception overhead does not vanish even for infinite block lengths.
The idea of overlapping generations, where some packets are shared among generations, has been proposed. This overlap reduces the reception overhead of SRLNC since generations can help each other in the decoding process. Another overlapped SRLNC scheme called Random Annex codes proposes random sharing of the packets between any two generations.
It should be noted that the overlap between different generations in overlapped SRLNC can be seen as having a repetition outer code acting on the common packets from overlapping generations. Thus, overlapped SRLNC can be seen as a special case of SRLNC with outer code. In overlapped SRLNC, in contrast to separate outer coding, there is no need to wait for the recovery of a large fraction of the generations before the repetition outer code can participate in the decoding. This can potentially reduce the reception overhead compared to other schemes. This point of view then leads to the idea of allowing the outer code to participate in the decoding, but not limiting the outer code to a repetition code. This in turn generates a host of new questions. For example, a major question is how one can design an outer code which provides minimum reception overhead. To the best of our knowledge, no general analysis and design technique for SRLNC with an outer code exists in the literature. Previous analysis methods either assume specific network structures or specific coding schemes and thus cannot be used to design outer coded SRLNC in a general way.
It should be noted that, for this document, the only limitation on the outer code is that we consider the class of linear outer codes which choose their variable nodes uniformly at random. These are referred to as random linear outer codes. This limitation simplifies the analysis and design of optimal codes. As will be discussed below, despite the mentioned limitation, the optimal design achieves asymptotic overheads as small as 2%.